import itertools
import copy
from time import time


# 计算数组中和为目标值的所有组合
def cal_sum(data_list, target):
    for i in range(1 << len(data_list)):    # 左移运算符，计算列表长度每个位置取或不取的组合数
        num_sum = 0
        tmp = ''
        for j in range(len(data_list)):
            if i & 1 << j:
                num_sum += data_list[j]
                tmp = str(data_list[j]) if tmp == '' else tmp + ' + ' + str(data_list[j])
        if num_sum == target:
            # print(i, bin(i))
            # print(tmp + ' = %.1f' % target)
            yield list(map(float, tmp.split(' + ')))


# 将数组分为n组,n=目标值个数,每组和为对应目标值,找到一个解就返回
def find_one(data_list, target_list):
    res_dic = {}
    # 递归部分
    def split_data(data_li, target_li, dic):
        if not (data_li or target_li):      # 数组和目标值全空了才返回真
            return True
        data = copy.deepcopy(data_li)
        target = copy.deepcopy(sorted(target_li))
        tar = target.pop()
        all_group = list(cal_sum(data, tar))  # 每个target的可能组合
        if not all_group:   # 递归无果时打断
            return False
        for j in all_group:     # 遍历每种可能
            copy_data = copy.deepcopy(data)
            dic[tar] = copy.deepcopy(j)
            while j:
                copy_data.remove(j.pop())  # 不断取出一个组合的全部值，从原始数组删去，传给下一次计算组合
            flag = split_data(copy_data, target, dic)
            if flag:
                return dic
    res = split_data(data_list, target_list, res_dic)
    return res


# 找到所有可能解
def find_all(data_list, target_list):
    res = list(map(lambda x: list(cal_sum(x[0], x[1])), [(data_list, tar) for tar in target_list]))
    for i in itertools.product(res[0], res[1], res[2]):
        new_ls = sum(i, [])
        res_li = []
        if len(set(new_ls)) == len(data_ls):
            for j in i:
                res_li.append({sum(j): j})
        if res_li:
            yield res_li


if __name__ == '__main__':
    data_ls = [269.1, 299, 358.8, 488.5, 538.2, 548.3, 627.9, 717.6, 956.8, 1046.5, 1166.1, 3019.9, 5076.3, 8461.7,
               8880.3, 13634.6]
    target_ls = [12498.2, 16856.9, 16734.5]

    t1 = time()
    a = find_one(data_ls, target_ls)
    t2 = time()
    # print(a)
    for i in a.items():
        print(i)
    print(t2-t1)

    t3 = time()
    b = find_all(data_ls, target_ls)
    for i in b:
        # print(list(i))
        for j in i:
            print(j)
        print()
    t4 = time()
    print(t4-t3)
